package com.guet;

import javax.swing.*; // 导入用于图形用户界面对话框的包
import java.text.DateFormat; // 导入用于日期格式化的包
import java.text.ParseException; // 导入用于处理解析异常的包
import java.text.SimpleDateFormat; // 导入用于简单日期格式化的包
import java.util.*; // 导入用于集合框架和其他实用程序的包

public class algorithm {
    public MGraph mGraph = new MGraph(); // 创建图对象
    public int driveTimeArgs[][] = new int[mGraph.vexNum * 2][mGraph.vexNum * 2]; // 创建用于保存驱动时间的二维数组
    int position[][] = new int[mGraph.vexNum * 2][mGraph.vexNum * 2]; // 创建用于保存位置的二维数组
    private int driveSpeed = 6; // 定义驾驶速度
    private int cycling = 4; // 定义骑行速度
    private int walkSpeed = 2; // 定义步行速度
    String times[] = {"当前时间", "00:00 ~ 11:15", "11:15 ~ 13:00",
            "13:00 ~ 14:00", "14:00 ~ 15:00", "15:00 ~ 17:35",
            "17:35 ~ 20:00", "20:00 ~ 21:40", "21:40 ~ 22:00", "22:00 ~ 24:00"}; // 定义时间段数组
    List<String> Crowded = new fileUse().getCrowded(); // 获取拥挤度信息
    private PathHistory pathHistory = new PathHistory(); // 新增路径历史记录

    public List<Integer> Dijkstra(String startName, String endName, String way) {
        List<Integer> result; // 定义结果列表
        if (way.contains("+")) { // 如果包含“+”，则使用多模式Dijkstra算法
            result = multiModeDijkstra(startName, endName, way);
        } else { // 否则，使用常规Dijkstra算法
            result = regularDijkstra(startName, endName, way);
        }
        if (result == null || result.isEmpty()) { // 如果结果为空或无效，显示对话框提示
            JOptionPane.showMessageDialog(null, "未找到有效路径: " + startName + " 到 " + endName);
        } else {
            pathHistory.addPathRecord(startName, endName, result, way); // 记录路径历史
        }
        return result; // 返回结果列表
    }

    private List<Integer> regularDijkstra(String startName, String endName, String way) {
        int start = getIdByName(startName); // 获取起点ID
        int end = getIdByName(endName); // 获取终点ID

        if (start == -1 || end == -1) { // 如果起点或终点无效，显示对话框提示
            JOptionPane.showMessageDialog(null, "无效的起点或终点");
            return null;
        }

        boolean[] selected = new boolean[mGraph.vexNum * 2]; // 定义已选择节点数组
        int[] minCost = new int[mGraph.vexNum * 2]; // 定义最小花费数组
        int[] parent = new int[mGraph.vexNum * 2]; // 定义父节点数组
        Arrays.fill(selected, false); // 初始化已选择节点数组为false
        Arrays.fill(minCost, Integer.MAX_VALUE); // 初始化最小花费数组为无穷大
        Arrays.fill(parent, -1); // 初始化父节点数组为-1
        minCost[start] = 0; // 设置起点的最小花费为0
        Queue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(o -> minCost[o])); // 定义优先队列
        queue.offer(start); // 将起点加入队列

        while (!queue.isEmpty()) { // 当队列不为空时循环
            int currentId = queue.poll(); // 获取队列中的最小值
            int[] directions = {mGraph.vexs.get(currentId).top, mGraph.vexs.get(currentId).bottom, mGraph.vexs.get(currentId).left, mGraph.vexs.get(currentId).right}; // 获取当前节点的所有方向
            for (int dir : directions) { // 遍历每个方向
                if (dir == -1) continue; // 如果方向无效，跳过
                int drive = way.equals("步行") ? 1 : mGraph.vexs.get(dir).drive; // 判断当前方式是否为步行
                if (drive >= (way.equals("骑行") ? 1 : (way.equals("驾车") ? 2 : 0)) && !selected[dir] && mGraph.arcs[currentId][dir] + minCost[currentId] < minCost[dir]) {
                    // 如果可以通过当前方式到达且未被选择且当前路径花费小于最小花费，更新最小花费和父节点，并将方向加入队列
                    minCost[dir] = mGraph.arcs[currentId][dir] + minCost[currentId];
                    parent[dir] = currentId;
                    queue.add(dir);
                }
            }
            selected[currentId] = true; // 标记当前节点为已选择
        }

        if (minCost[end] == Integer.MAX_VALUE) { // 如果终点的最小花费仍为无穷大，返回null
            return null;
        }
        List<Integer> path = new LinkedList<>(); // 定义路径列表
        for (int at = end; at != -1; at = parent[at]) { // 从终点回溯父节点，构建路径
            path.add(at);
        }
        Collections.reverse(path); // 反转路径，使其从起点到终点

        return path; // 返回路径列表
    }

    public List<Integer> multiModeDijkstra(String startName, String endName, String way) {
        // 首先使用纯步行方式计算初始路径
        List<Integer> initialPath = regularDijkstra(startName, endName, "步行");
        if (initialPath == null || initialPath.isEmpty()) {
            return null;
        }

        List<Integer> optimizedPath = new LinkedList<>(); // 定义优化后的路径列表
        String[] modes = way.split("\\+"); // 分割传入的方式字符串
        String preferredMode = modes[1]; // 首选模式（骑行或驾车）

        for (int i = 0; i < initialPath.size() - 1; i++) {
            int currentId = initialPath.get(i); // 获取当前节点ID
            int nextId = initialPath.get(i + 1); // 获取下一个节点ID

            // 先添加当前节点
            optimizedPath.add(currentId);

            // 检查相邻两点是否可以骑行或驾车
            if ((preferredMode.equals("骑行") && mGraph.vexs.get(currentId).drive >= 1 && mGraph.vexs.get(nextId).drive >= 1) ||
                    (preferredMode.equals("驾车") && mGraph.vexs.get(currentId).drive >= 2 && mGraph.vexs.get(nextId).drive >= 2)) {

                // 使用相应的方式替换路径中的该段
                int tempCost = mGraph.arcs[currentId][nextId]; // 获取当前段的花费
                List<Integer> subPath = regularDijkstra(mGraph.vexs.get(currentId).name, mGraph.vexs.get(nextId).name, preferredMode); // 计算子路径
                if (subPath != null && !subPath.isEmpty()) {
                    optimizedPath.addAll(subPath.subList(1, subPath.size())); // 添加替换的子路径（不包括起始点）
                    continue; // 跳过后续的步行添加
                }
            }
        }

        // 确保最后一个节点添加到路径中
        if (!optimizedPath.contains(initialPath.get(initialPath.size() - 1))) {
            optimizedPath.add(initialPath.get(initialPath.size() - 1));
        }

        return optimizedPath; // 返回优化后的路径列表
    }

    public List<Integer> Floyd(String startName, String endName) {
        int start = getIdByName(startName); // 获取起点ID
        int end = getIdByName(endName); // 获取终点ID

        if (start == -1 || end == -1) { // 如果起点或终点无效，显示对话框提示
            JOptionPane.showMessageDialog(null, "无效的起点或终点");
            return null;
        }

        initializeFloydWarshall(); // 初始化Floyd-Warshall算法

        List<Integer> path = new ArrayList<>(); // 定义路径列表
        if (driveTimeArgs[start][end] == Integer.MAX_VALUE) { // 如果起点到终点无法到达，显示对话框提示
            JOptionPane.showMessageDialog(null, "无法到达: " + startName + " 到 " + endName);
            return null;
        }

        path.add(start); // 添加起点到路径
        while (position[start][end] != end) { // 通过位置数组构建路径
            start = position[start][end];
            path.add(start);
        }
        path.add(end); // 添加终点到路径
        return path; // 返回路径列表
    }

    private void initializeFloydWarshall() {
        for (int i = 0; i < mGraph.vexNum * 2; i++) { // 初始化driveTimeArgs和position数组
            for (int j = 0; j < mGraph.vexNum * 2; j++) {
                driveTimeArgs[i][j] = i == j ? 0 : Integer.MAX_VALUE; // 如果i==j, 设置为0，否则设置为无穷大
                position[i][j] = j; // 初始位置为j
            }
        }

        for (vexsinfo v : mGraph.vexs.values()) { // 遍历图中每个节点的信息
            int dir[] = {v.left, v.right, v.top, v.bottom}; // 获取节点的四个方向
            for (int i = 0; i < 4; i++) { // 遍历每个方向
                if (dir[i] == -1) continue; // 如果方向无效，跳过
                vexsinfo v1 = mGraph.vexs.get(dir[i]); // 获取相邻节点的信息
                if (v1.drive == 0) continue; // 如果相邻节点不可通行，跳过
                int speed = driveSpeed / (int) Math.max(v.croded_level, v1.croded_level); // 计算速度
                int t = mGraph.arcs[v.id][v1.id] / speed + 1; // 计算时间
                driveTimeArgs[v.id][v1.id] = t; // 更新driveTimeArgs数组
            }
        }

        for (int k = 0; k < mGraph.vexNum * 2; k++) { // Floyd-Warshall算法主循环
            for (int i = 0; i < mGraph.vexNum * 2; i++) {
                for (int j = 0; j < mGraph.vexNum * 2; j++) {
                    if (driveTimeArgs[i][k] != Integer.MAX_VALUE && driveTimeArgs[k][j] != Integer.MAX_VALUE &&
                            driveTimeArgs[i][k] + driveTimeArgs[k][j] < driveTimeArgs[i][j]) {
                        // 如果通过节点k的路径比直接的路径更短，更新driveTimeArgs和position数组
                        driveTimeArgs[i][j] = driveTimeArgs[i][k] + driveTimeArgs[k][j];
                        position[i][j] = position[i][k];
                    }
                }
            }
        }
    }

    private int getIdByName(String name) {
        for (vexsinfo v : mGraph.vexs.values()) { // 遍历图中每个节点的信息
            if (v.name.equals(name)) { // 如果节点名称匹配，返回节点ID
                return v.id;
            }
        }
        return -1; // 如果没有匹配的节点，返回-1
    }

    public int getListIdsDistance(List<Integer> ids) {
        if (ids == null || ids.size() < 2) { // 如果ID列表为空或元素少于2个，返回0
            return 0;
        }
        int distance = 0; // 初始化距离
        for (int i = 1; i < ids.size(); i++) { // 遍历ID列表
            distance += mGraph.arcs[ids.get(i)][ids.get(i - 1)]; // 累加相邻节点的距离
        }
        return distance; // 返回总距离
    }

    public void setCrowdingDegree(String periodFind) {
        int periodIndex = getWhereInTimes(periodFind); // 获取时间段索引
        for (vexsinfo v : mGraph.vexs.values()) { // 遍历图中每个节点的信息
            if (periodIndex % 2 != 0) { // 如果时间段索引为奇数
                v.croded_level = 1.0F; // 设置拥挤度为1.0
            } else if (Crowded.contains(v.name)) { // 如果节点名称在拥挤列表中
                v.croded_level = 2.0F; // 设置拥挤度为2.0
            } else {
                v.croded_level = 1.0F; // 否则设置拥挤度为1.0
            }
        }
    }

    public int getWhereInTimes(String periodFind) {
        if (periodFind.equals("当前时间")) { // 如果输入为“当前时间”
            Date now = new Date(); // 获取当前日期时间
            DateFormat df = new SimpleDateFormat("HH:mm"); // 定义时间格式
            periodFind = df.format(now); // 格式化当前时间
        }

        int periodIndex = -1; // 初始化时间段索引
        DateFormat df = new SimpleDateFormat("HH:mm"); // 定义时间格式
        try {
            Date periodTime = df.parse(periodFind); // 解析输入时间
            for (int i = 1; i < times.length; i++) { // 遍历时间段数组
                Date time = df.parse(times[i].split(" ~ ")[0]); // 解析时间段开始时间
                if (periodTime.before(time)) { // 如果输入时间早于时间段开始时间
                    periodIndex = i - 1; // 更新时间段索引
                    break;
                }
            }
        } catch (ParseException e) {
            e.printStackTrace(); // 捕获并打印解析异常
        }
        return periodIndex; // 返回时间段索引
    }

    public double getSpeed(String goWay, String periodFind, int startId, int positionId) {
        setCrowdingDegree(periodFind); // 设置拥挤度
        int speed = goWay.equals("步行") ? walkSpeed : goWay.equals("骑行") ? cycling : driveSpeed; // 获取相应的速度
        return speed / Math.max(mGraph.vexs.get(positionId).croded_level, mGraph.vexs.get(startId).croded_level); // 返回调整后的速度
    }

    public int getTwoPTime(String startName, String endName) {
        int start = getIdByName(startName); // 获取起点ID
        int end = getIdByName(endName); // 获取终点ID
        return driveTimeArgs[start][end]; // 返回起点到终点的时间
    }

    public int getListTime(List<Integer> ids, String goWay, String period) {
        if (ids == null || ids.size() < 2) { // 如果ID列表为空或元素少于2个，返回0
            return 0;
        }
        double totalTime = 0; // 初始化总时间
        for (int i = 1; i < ids.size(); i++) { // 遍历ID列表
            int start = ids.get(i - 1); // 获取起点ID
            int end = ids.get(i); // 获取终点ID
            totalTime += mGraph.arcs[start][end] / getSpeed(goWay, period, start, end); // 累加每段距离所需时间
        }
        return (int) totalTime; // 返回总时间
    }

    public String messageCrowded(List<Integer> list, String time) {
        if (list == null || list.isEmpty()) { // 如果ID列表为空或无效，返回空字符串
            return "";
        }

        setCrowdingDegree(time); // 设置拥挤度
        for (int id : list) { // 遍历ID列表
            if (mGraph.vexs.get(id).croded_level > 1.5) { // 如果节点的拥挤度大于1.5
                return "提示：该条路线存在上下课高峰期路段"; // 返回提示信息
            }
        }
        if (time.equals(times[0])) { // 如果时间为当前时间
            String currentTime = new SimpleDateFormat("HH:mm").format(new Date()); // 获取当前时间
            int hour = Integer.parseInt(currentTime.split(":")[0]); // 获取当前小时
            int minute = Integer.parseInt(currentTime.split(":")[1]) + 10; // 获取当前分钟并加10
            if (minute >= 60) { // 如果分钟大于等于60，小时加1，分钟减60
                hour++;
                minute -= 60;
            }
            String futureTime = String.format("%02d:%02d", hour, minute); // 格式化未来时间
            int periodIndex = getWhereInTimes(futureTime); // 获取未来时间段索引
            if (periodIndex % 2 == 0) { // 如果未来时间段索引为偶数
                return "该路线十分钟后可能存在高峰路段"; // 返回提示信息
            }
        }
        return ""; // 返回空字符串
    }

    public PathHistory getPathHistory() {
        return pathHistory;
    }
}
